"""
https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/
"""

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        def bfs(level):
            next_level = []
            if not level: return
            legth = len(level)
            for i in range(legth):
                node = level.pop()
                if not node: continue
                if i < legth - 1:
                    node.next = level[-1]
                if node.left:
                    next_level.insert(0, node.left)
                if node.right:
                    next_level.insert(0, node.right)
            bfs(next_level)
        bfs([root])
        return root

    # stack = [root]
    # while stack:
    #     for i in range(len(stack)):
    #         node = stack.pop()
    #         if not node: continue
    #         if node.left:
    #             stack.insert(0, node.left)
    #         if node.right:
    #             stack.insert(0, node.right)
    #     for index, j in enumerate(stack[::-1]):
    #         if index < len(stack) - 1:
    #             j.next = stack[::-1][index + 1]
    # return root




